/**
 * 312. 戳气球
 * https://leetcode-cn.com/problems/burst-balloons/
 */

/**
 * @param {number[]} nums
 * @return {number}
 */
function maxCoins(nums) {
  nums = [1, ...nums, 1];
  const dp = new Array(nums.length);
  for (let i = 0; i < dp.length; i += 1) {
    dp[i] = new Array(nums.length).fill(0);
  }
  for (let j = 2; j < nums.length; j += 1) {
    for (let i = j - 2; i >= 0; i -= 1) {
      let max = 0;
      for (let k = i + 1; k < j; k += 1) {
        const count = nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j];
        if (count > max) {
          max = count;
        }
      }
      dp[i][j] = max;
    }
  }
  return dp[0][nums.length - 1];
}

console.log(maxCoins([1, 5]) === 10);
console.log(maxCoins([5]) === 5);
console.log(maxCoins([3, 1, 5]) === 35);
console.log(maxCoins([3, 1, 5, 8]) === 167);
